package liangtWorkSpace.suanfa;

/**
 * 快速排序
 *      双边快排
 *      对比两边大小
 */
public class QuickSort {

    public static void main(String[] args) {
//        int arrs[] = {7,3,2,8,10,9,5,4,6,1,6};
        int arrs[] = SortUtils.getArrays(1000);
        int[] arrs2 = new int[arrs.length];
        System.arraycopy(arrs,0,arrs2,0,arrs.length);

        sort(arrs,0,arrs.length-1);
        System.out.println(SortUtils.check(arrs,arrs2));
        SortUtils.print(arrs);
    }

    /**
     * 快速排序
     * @param arrs
     */
    private static void sort(int[] arrs,int left,int right){
        if (left >= right){
            return;
        }

        int min = partition(arrs,left,right);
        sort(arrs,left,min-1);
        sort(arrs,min+1,right);
    }

    //快速排序
    private static int partition(int[] arrs, int left, int right) {
        int privot = arrs[right];

        int le = left;
        int re = right - 1;

        while ( le <= re){
            while (arrs[le] <= privot && le <= re){
                le++;
            }
            while (arrs[re] >= privot && le < re){
                re--;
            }
            if (le < re){
                SortUtils.swap(le,re,arrs);
            }
        }
        SortUtils.swap(le,right,arrs);
        return le;
    }
}
